class TrieNode:
    # Initialize your data structure here.
    def __init__(self, val=None):
        self.childen = {}
    
    def hasChild(self, ch):
        return (ch in self.childen)

    # @param {char} ch
    # @return {list} The list of sons
    def child_list(self, ch):
    	if ch != '.':
    		if ch in self.childen:
    			return [self.childen[ch]]
    		else:
    			return []
    	else:
    		return [v for v in self.childen.itervalues() if v is not None]
    		


class WordDictionary:
	def __init__(self):
		self.root = TrieNode()

	# @param {string} word
	# @return {void}
	# Adds a word into the data structure.
	def addWord(self, word):
		r = self.root
		for c in word:
			if not r.hasChild(c):
				r.childen[c] = TrieNode()
			r = r.childen[c]
		r.childen[None] = None

	# locate the word/prefix
	# @param {string} word
	# @return {TrieNode, None}
	def locate(self, word, parrent):
		if len(word) == 0:
			return [parrent]
		cl = parrent.child_list(word[0])
		loc_list = []
		for son in cl:
			if son:
				loc_list.extend(self.locate(word[1:], son))
		return loc_list

	# @param {string} word
	# @return {boolean}
	# Returns if the word is in the data structure. A word could
	# contain the dot character '.' to represent any one letter.
	def search(self, word):
		el = self.locate(word, self.root)
		good = False
		for e in el:
			if None in e.childen:
				good = True
				break
		return good


# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

if __name__ == '__main__':
	wordDictionary = WordDictionary()
	for word in ['acb', 'acd', 'adb', 'af', '']:
		wordDictionary.addWord(word)
	print wordDictionary.search("")